1. Field of the Invention
The present invention relates generally to methods, apparatuses, and software products for processing images, and more particularly to computer-implemented methods and software products for interpolating shapes between key posed shapes of a two- or three-dimensional geometric model.
2. Description of the Background Art
In computer graphics technology, a two- or three-dimensional geometric model is a self-contained object or entity that can be represented by a connected set of points. A geometric model can be a simple structure such as a circle or sphere, or can be something much more complex, such as an animal's body. A model is set up so that it can be manipulated into different shapes. A shape is used as a pose of the model at a specific time during a computer-animated sequence.
One way for a computer animator to animate the movement of a geometric model from one position to another is to put the model into a start pose, store it, put the model into a pose slightly closer to the final pose, store it, put it into a pose slightly closer to the final pose, store it, and so on, until the final pose is reached. The model's movement is animated when the poses are quickly replayed in succession. The process of creating all the separate poses is very tedious and inefficient, as it is equivalent to drawing separate frames one at a time using traditional animation tools.
A much faster and more effective way to animate a model's movement is for the animator to first prepare a "library" of different shapes of the model to be used in the animation, then pick the appropriate shapes from this shape library to create a series of "key" poses (often simply referred to as "keys") to appear at specific times. The computer graphics hardware and software is then employed to interpolate the shapes between the key poses (often referred to as "inbetween shapes," or more simply, "inbetween"). For example, to animate a hand waving from left to right, the animator sets two key poses of the hand, one key pose at the left position and one key pose at the right position. The computer then interpolates the intermediate shapes of the hand moving across from left to center to right.
This process of specifying sets of data at specific times and using the computer to generate the inbetween data is a fundamental procedure in computer animation known as "key-frame interpolation." Key-frame interpolation is most often applied to sets of data that are single valued, such as a particular angle of rotation, or points in two- or three-dimensions. A more specific application, where the data posed and interpolated is a set of two- or three-dimensional geometric models is commonly referred to as "shape interpolation."
In order to interpolate the shapes between the key poses of a model, there needs to be a way to specify the influence of the key poses on the inbetween shapes. This is most often done implicitly by using a particular type of parametric interpolation curve, where, in this case, the parameter is time. Each inbetween shape can be considered analogous to a sample point on an interpolation curve. Just as the sample point in the curve can be computed as a weighted combination of the key points defining the curve, so can the inbetween shape be computed as a weighted combination of the key poses. The amounts of these weights for each inbetween shape and the way in which the weights vary depend on the type of curve used. For example, using a linear curve between two key poses defines the inbetween shapes in terms of only two key poses: the poses before and after (in terms of time) the desired inbetween shape. Since a linear curve does not provide a "smooth" interpolation, it is common practice in computer graphics and other applications to use parametric cubic curves to interpolate inbetween shapes. This means that four points contribute to each inbetween shape: the two poses before and the two poses after the inbetween. The way in which these four key poses influence a particular inbetween shape depends on the type of parametric cubic curve employed.
Several curve types are used in the more general process of key-frame interpolation of single values or points in two or three dimensions, but not all of these types are applicable to the particular problems of shape interpolation. In key-frame interpolation, Bezier curves are a popular choice because they interpolate between the key data and provide two additional sets of data with which to change the affects on the inbetween data. These additional points (or "handles") are not interpolated, but provide particularly intuitive control of two- or three-dimensional curves. For single-valued or point data, this is an effective and intuitive technique for interpolating single values or points.
However, Bezier curves are not suitable for shape interpolation because the two additional "handle shapes" must be copies of the entire geometric model, requiring considerable extra data storage for many complex models. Second, since these handles are shapes which are never interpolated, the animator must painstakingly position a complex geometric model into a pose that is never desired as part of the final animation but has the indirect effect on the inbetween shapes. These poses may have to be repeatedly adjusted to achieve the correct inbetween shapes. The space required to store these handle shapes, the difficulty of the general process of shaping a geometric model, and the lack of intuitive control that this offers all make Bezier curves unsuitable for shape interpolation.
The more commonly used curve types for shape interpolation are those for which all key poses are interpolated and no other poses are necessary to define the inbetween shapes. For a curve type to meet these requirements would seem to give it little flexibility, and this is often the case. Given a set of key poses and an interpolation curve to generate the inbetween shapes, if a sequence of the inbetween shapes is not desirable, there are no additional controls to affect the inbetween shapes without changing the key poses themselves, which again requires extensive effort by the animator. For example, in FIG. 1A, there is shown a position over time graph of key poses P.sub.0 -P.sub.3 of a point at times t.sub.0 to t.sub.3. The desired path of interpolation is a straight line 110 between t.sub.1 and t.sub.2. However, with a conventional interpolation curve defined at points P.sub.0 through P.sub.3, the curve overshoots 100, such that the interpolated points are above the existing key points and the desired path 110.
Because overshoots are undesirable in key-frame and shape interpolation, the common workaround is to introduce another key pose between two existing keys to guide the inbetween shapes in the more desired direction along line 110. This workaround is illustrated in FIG. 1B, where another key pose P* is added between P.sub.1 and P.sub.2. The introduction of P* reduces the overshoot 100 demonstrated in FIG. 1A, but smaller overshoots 100 (FIG. 1B) in the intervals between P.sub.1 and P*, and P* and P.sub.2 still occur, here producing an even less desirable result in terms of the smoothness of the interpolated path: an animated object moving across the screen between points P1 and P2 would zigzag through P* instead of moving in a straight-line or smooth curve. If this workaround was not required very often it would be an acceptable solution, but experience has shown that many additional key poses are often necessary to achieve the desired inbetween shapes, which leads back to the space and labor requirements of shaping and storing many additional poses.
One way of dealing with this problem in conventional animation systems provides the animator with curves for each point in the model in order to adjust the inbetween shapes. This trades off the space and labor requirements of generating additional poses with that of creating as many curves as there are points in the model (often many thousands) and requiring the animator to select and adjust those that are necessary, which is likely to a be large portion, if not all such curves. This alternative approach provides no savings in computer memory since a curve must be defined for each point of the model, or human labor, since so many curves have to be manually adjusted.
Another way of dealing with this problem takes away the specification of a particular curve type through the poses and allows the animator to specify weighting curves for each pose. The animator is presented with a timeline and a set of curves for each key pose that define the contribution of each pose to the inbetween shapes. The contribution of each pose is defined by a weight, and each inbetween shape is the weighted sum of the key poses, adjusted for the relative time of the inbetween shape to the key poses. This has proven to be an awkward interface for animators since it provides a very mathematical interface to solving the problem. If a mathematician was to plot the weighting curves for each pose that result from a standard interpolation scheme, it turns out that many poses actually have negative contributions to some inbetween shapes, which is not an intuitively obvious result. This lack of intuition makes this an ineffective interface for animators to use to graphically define the weighting curves.
A variety of additional curve types have been developed for use in key-frame interpolation that offer additional shaping control at each key frame or point. This control is often presented in the form of local shape parameters, which are sets of one or more values specified at each key that affect the shape of the curves on either side of each key point. Such curve types have a default set of values that yield a familiar interpolation curve, such as a Catmull-Rom spline, and therefore provide additional control to complement a familiar result. Although not used in shape interpolation, their advantage in this application lies in the fact that the shape parameters usually consist of one to three values that can be applied to data or shapes with an arbitrary number of dimensions, unlike Bezier curves where the handles must be of the same dimension as the data being interpolated.
Conventional interpolation curves using shape parameters attempt to offer intuitive control of the curve by affecting properties of the tangent vectors at the key frames or points. At a given key there are considered to be two tangent vectors to the curve: one "incoming" vector that approaches from the previous key and a second "outgoing" vector that departs towards the next key. The properties of these vectors that are most desirable to control at these points are their common direction, their absolute magnitudes and their relative magnitudes. These properties of the tangent vectors at a key are determined by a relationship between the key itself and the previous and next key. The Catmull-Rom spline, for example, ignores the position of the key itself and defines the tangents as the vector between the previous and next key. These vectors are not explicitly derived but are achieved through the mathematical formulation of the curve types.
The shape parameters offer additional freedom in these formulations of how the properties of the tangent vectors are controlled. A common shape parameter is named "tension" and controls the magnitude of both of the tangent vectors. In some cases, however, the conventional tension parameter also simultaneously alters the direction of the tangent vectors. A less common shape parameter is given the name "bias" and may control the relative magnitudes of these vectors, their direction, or both at once, depending on the curve type. Shape parameters that affect more than one of these properties at once are considered non-intuitive to animators, because in attempting to change one property, such as the magnitude of the tangent vectors, the conventional shape parameter will alter another property, such as the direction, producing a different result than intended by the animator. No existing curve type provides both isolated and intuitive control of these three properties.
The shortcomings of the existing shape interpolation techniques make it is difficult and time consuming for the computer animator to control the interpolated shapes between the key poses. Existing techniques for affecting the inbetween shapes involve either adding and reshaping many new poses or individually editing the hundreds or thousands of curves through each key point in the sequence of poses. These techniques are expensive in terms of data storage and manipulation time. Other techniques developed to avoid these expenses are not intuitive to the animators. Thus, there is a need for an improved method for shape interpolation that overcomes the disadvantages of the conventional techniques. Because the need for shape interpolations between key poses in geometric models is commonly experienced in the computer animation, it is desirable to provide a simplified technique with a small and independent set of shape parameters to control the form of the curve on which the interpolation is based, without the need to modify existing modeling and animation tools.